package com.dy.分类.链表.反转链表2;


/**
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;
        ListNode p = head;
        int len = n - m;
        ListNode headPre = null;
        while (p != null && m - 1 > 0) {
            headPre = p;  //开始逆置的前一个节点
            p = p.next;
            m--;
        }
        ListNode reverseHead = p;//逆置的第一个节点
        //开始逆置
        ListNode current = p;
        ListNode tail = null;

        while (current != null && len >= 0) {
            ListNode next = current.next;
            current.next = tail;
            tail = current;  //逆置的最后一个节点
            current = next; //逆置的最后一个节点的下一个节点
            len--;
        }
        if (headPre == null) {
            head = tail;
        } else {
            headPre.next = tail;
        }
        reverseHead.next = current;
        return head;


    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode a = new ListNode(1);
        a.next = new ListNode(2);
        a.next.next = new ListNode(3);
        a.next.next.next = new ListNode(4);
        a.next.next.next.next = new ListNode(5);

        ListNode head = solution.reverseBetween(a, 1, 2);
        int i = 0;
        System.out.println();
    }
}
